package leetcode.array.permutation;

import java.util.ArrayList;
import java.util.List;

/**
 * 46. 全排列
 *
 *
 */
public class Permute {

    private List<List<Integer>> lists = new ArrayList<>();

    public static void main(String[] args) {
        Permute solution = new Permute();
        int[] nums = {1,2,3,4};
        List<List<Integer>>  resList = solution.permute(nums);
        System.out.println(resList);
    }

    /**
     * 全排列
     *
     * @param nums 数组
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        List<Integer> list = new ArrayList<>(n);
        boolean[] used = new boolean[n];
        int count = 0;
        backtrace(list, used, count, nums);
        return lists;
    }

    /**
     * 回溯法实现全排列
     *
     * @param list      临时存储结果元素的 List对象 (会随着回溯往前删除尾部的元素)
     * @param used      标记数组
     * @param count     记录排列中已确定的元素个数
     * @param nums      原数组
     */
    public void backtrace(List<Integer> list, boolean[] used, int count, int[] nums) {
        if (count == nums.length) {
            lists.add(new ArrayList(list));
            return;
        }
        for (int i = 0; i < used.length; i++) {
            if (!used[i]) {
                list.add(nums[i]);
                used[i] = true;
                backtrace(list, used, count + 1, nums);
                // 在回到上一层节点的时候, 需要进行回溯操作 把状态变量回退到未进行下一层遍历操作的状态值
                list.remove(list.size() - 1);
                used[i] = false;
            }
        }
    }
}
